題目連結(https://leetcode.com/problems/jump-game/description/)

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

Return true if you can reach the last index starting from index 0, or false otherwise.

今天分享的這題我一開始想到的是 DP，但其實用 greedy 解比較快，所以來分享一下兩種方法的程式碼與比較

1. Repeat（題目重複確認）

• 輸入：integer array nums 每個數字代表從當前位置可跳的最大長度
• 輸出：true 如果從 index 0 開始可達最終索引，不行則回傳 false
• 前提：
  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

2. Examples（舉例確認理解）

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [3,2,1,0,4]
Output: false
Explanation: 不管從 0,1,2 開始跳都會經過 3, 但 3 沒有跳躍步長

3. Approach（解題思路）

方法 1：DP

• 我認為不太像DP，因為沒有明確的狀態轉移方程，比較像是陣列標記法/BFS，但 LeetCode 分類DP（寬鬆）
• 時間複雜度：O(n^2)
• 空間複雜度：O(n)

方法 2：Greedy

• 用一個變數 maxreach 不斷去更新能跳到的最遠位置
• 時間複雜度：O(n)
• 空間複雜度：O(1)

4. Code（C++）

方法 1：DP

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size() - 1;
        vector<bool> dp(n+1, false); //至少要有1個空間，不然[0]的測資會錯誤
        dp[0] = true;
        for(int i = 0; i < n; i++){
            if(!dp[i]) continue; // 如果當前位置不能到達，跳過
            for(int j = 1; j <= nums[i] && i+j <= n; j++){
		            //從位置 i 跳 j 步到 i+j
                dp[i+j] = true; //從 i+1 到 n 設成可達(在 nums[i] 還沒用完之前）
            }
        }
        return dp[n];
    }
};

方法 2：Greedy(由前往後）

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size() - 1;
        int maxreach = 0;
        for(int i = 0; i <= n; i++){
            if(i > maxreach) return false; // 如果當前位置超過了能到達的最遠位置，返回 false
            maxreach = max(maxreach, i + nums[i]);// 更新能到達的最遠位置
        }
        return true;
    }
};

方法 3: 貪心算法（從後往前）

    // 時間: O(n), 空間: O(1)
    bool canJump_Backward(vector<int>& nums) {
        int n = nums.size() - 1;
        int lastPos = n;  // 目標位置
        
        // 從倒數第二個位置開始往前檢查
        for (int i = n - 1; i >= 0; i--) {
            // 如果從位置 i 能跳到目標位置
            if (i + nums[i] >= lastPos) {
                lastPos = i;  // 更新目標位置
            }
        }
        
        return lastPos == 0;
    }

5. Test 範例

範例: nums = [3, 2, 1, 0, 4]
索引:          0  1  2  3  4

視覺化過程:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
起點: 0
      ↓
dp = [T, F, F, F, F]

從 i=0 (可達) 跳躍:
         ↓  ↓  ↓
dp = [T, T, T, T, F]

從 i=1 (可達) 跳躍:
            ↓  ↓
dp = [T, T, T, T, F]

從 i=2 (可達) 跳躍:
               ↓
dp = [T, T, T, T, F]

i=3 (可達): nums[3]=0，跳不到任何地方
dp = [T, T, T, T, F]

i=4 (不可達): ❌ 跳過！
         因為 dp[4]=F
         我們根本沒有到達 i=4
         所以不需要考慮從 i=4 能跳去哪

範例: [2, 3, 1, 1, 4]
n = 4

i=0: maxreach=2, 2>=4? No, 繼續
i=1: maxreach=4, 4>=4? Yes → return true ✓
     ↑
     在這裡就返回了！

nums = [3, 2, 1, 0, 4]
索引:    0  1  2  3  4

反向檢查:
i=3: 3+0=3 < 4 ✗ 跳不到，lastPos 還是 4
i=2: 2+1=3 < 4 ✗ 跳不到，lastPos 還是 4  
i=1: 1+2=3 < 4 ✗ 跳不到，lastPos 還是 4
i=0: 0+3=3 < 4 ✗ 跳不到，lastPos 還是 4

最終 lastPos = 4 ≠ 0
結論: 無法從 0 到達 4 ✓ 正確！

6. 相關題目與延伸概念

45. Jump Game II

1306. Jump Game III

1871. Jump Game VII

7. 補充：語法＆注意事項

1. 為什麼可以 continue？

if dp[i] == false:
    代表: 從起點無法到達位置 i
    推論: 我們永遠不會站在位置 i
    結論: 討論「從位置 i 能跳去哪」毫無意義
    行動: 直接跳過 (continue)

實際執行流程

i=0: dp[0]=true  ✓ 執行內層迴圈，標記可達位置
i=1: dp[1]=true  ✓ 執行內層迴圈，標記可達位置
i=2: dp[2]=false ✗ continue，跳過內層迴圈
i=3: dp[3]=false ✗ continue，跳過內層迴圈
i=4: dp[4]=true  ✓ 執行內層迴圈，標記可達位置

正確性分析

for(int i = 0; i < n; i++){
    if(!dp[i]) continue; *// ✓ 避免做不避免運算，不是必須*
    for(int j = 1; j <= nums[i] && i+j <= n; j++){
        dp[i+j] = true;
    }
}

2. Greedy

由前往後
maxreach = max(maxreach, i + nums[i]);// 更新能到達的最遠位置

由後往前
原問題: 能否從 0 到達 n？

如果從 i 能跳到 n:
  新問題: 能否從 0 到達 i？
  
如果從 j 能跳到 i:
  新問題: 能否從 0 到達 j？
  
... 持續簡化 ...

如果最終簡化到: 能否從 0 到達 0？
  答案: YES！因為已經在起點了

ps. 部分內容經 AI 協助整理